package com.ljy.my_study.动态规划.找零钱;
/** 
* @author James
* @date 2018年6月19日 
*/
public class TestMain {
	/**
	 * 有数组penny，penny中所有的值都为正数且不重复。
	 * 每个值代表一种面值的货币，每种面值的货币可以使用任意张，
	 * 再给定一个整数aim(小于等于1000)代表要找的钱数，求换钱有多少种方法。
	 * 给定数组penny及它的大小(小于等于50)，同时给定一个整数aim，请返回有多少种方法可以凑成aim。
	 * 测试样例：
	 * [1,2,4],3,3
	 * 返回：2
	 * @param args
	 */
	public static void main(String[] args) {
		/**
		 * 分析：
		 * 设前n种货币凑成m（钱数）的方法数为dp[n][m],
		 * 1.使用第n种货币：dp[n][m]=dp[n-1][m]+dp[n-1][m-penney[n]];
		 * 2.不使用第n种货币：dp[n][m]=dp[n-1][m]（penney[n]>m）
		 * 
		 */
		int[] penney= {1,2,4,5};//币种数组
		int m=10;//要找的钱
		int[][] result=new int[penney.length+1][m+1];
		for(int i=0;i<result.length;i++) {
			for(int j=0;j<result[0].length;j++) {
				
			}
		}
		
	}
}
